package com.leetcode.sort;

/**
 * @author Dennis Li
 * @date 2020/7/24 22:49
 */
public class SortColors_75 {

    public void sortColors(int[] nums) {
        int zero = 0, two = nums.length - 1;
        int index = 0;
        while (index < nums.length) {
            if (index >= zero && nums[index] == 0) {
                swap(nums, zero++, index++);
                // 需要保证当前index比two小才更新
            } else if (two > index && nums[index] == 2) {
                // 放到顶端不需要再让index++
                swap(nums, two--, index);
            } else {
                index++;
            }
        }
    }

    public void sortColors2(int[] nums) {
        int zeros = traverse(nums, 0, 0);
        traverse(nums, 1, zeros);
    }

    private int traverse(int[] nums, int target, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            if (nums[i] != target && nums[j] == target) {
                swap(nums, i, j);
                i++;
                j--;
                continue;
            }
            if (nums[i] == target) {
                i++;
            }
            if (nums[j] != target) {
                j--;
            }
        }
        int k;
        for (k = 0; k < nums.length; k++) {
            if (nums[k] != target) break;
        }
        return k;
    }



    public void swap(int[] nums, int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

}
